home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk10.zip / QSORT.AWK < prev    next >
Text File  |  1991-10-05  |  1KB  |  79 lines
  1.  
  2.  
  3. # qsort text files
  4. #
  5.  
  6. function middle(x,y,z)  #return middle of 3
  7. {
  8.   if ( x <= y )  
  9.   { if ( z >= y )  return y
  10.     if ( z <  x )  return x
  11.     return z
  12.   }
  13.  
  14.   if ( z >= x )  return x
  15.   if ( z <  y )  return y
  16.   return z
  17. }
  18.  
  19.  
  20. function  isort(A , n,    i, j, hold)
  21. {
  22.   # if needed a sentinal at A[0] will be created
  23.  
  24.   for( i = 2 ; i <= n ; i++)
  25.   {
  26.     hold = A[ j = i ]
  27.     while ( A[j-1] > hold )
  28.     { j-- ; A[j+1] = A[j] }
  29.  
  30.     A[j] = hold
  31.   }
  32. }
  33.  
  34.  
  35. # recursive quicksort
  36. function  qsort(A, left, right    ,i , j, pivot, hold)
  37. {
  38.   
  39.   pivot = middle(A[left], A[int((left+right)/2)], A[right])
  40.  
  41.   i = left
  42.   j = right
  43.  
  44.   while ( i <= j )
  45.   {
  46.     while ( A[i] < pivot )  i++ 
  47.     while ( A[j] > pivot )  j--
  48.  
  49.     if ( i <= j )
  50.     { hold = A[i]
  51.       A[i++] = A[j]
  52.       A[j--] = hold
  53.     }
  54.   }
  55.  
  56.   if ( j - left > BLOCK )  qsort(A,left,j)
  57.   if ( right - i > BLOCK )  qsort(A,i,right)
  58. }
  59.  
  60. BEGIN { BLOCK = 5 }
  61.  
  62.  
  63. { line[NR] = $0 ""   # sort as string
  64. }
  65.  
  66. END  {
  67.  
  68.   if ( NR > BLOCK )  qsort(line, 1, NR)
  69.  
  70.   isort(line, NR)
  71.  
  72.   for(i = 1 ; i <= NR ; i++) print line[i]
  73. }
  74.   
  75.  
  76.  
  77.  
  78.     
  79.